package interview.algortithm;

/**
 * @Author: zhangrongqing
 * @Date: 2020/5/16 14:33
 * 在一个数组内查找元素，该数组是由升序序列截断成两段后反转拼接而成，例如5689123
 */
public class NumberLocate {

    public int findNumber(int[] numberArray , int number , int start , int end){
        int middle = (start + end)/2;

        if(numberArray[middle] == number){
            return middle;
        }

        //如果中间值已经算不出了那就是没有这个值，默认0
        if(middle == start){
            if(numberArray[end] == number){
                return end;
            }
            return 0;
        }

        //前半部分是正常序列
        if(numberArray[start] < numberArray[middle]){
            if(number >= numberArray[middle]){
                return findNumber(numberArray , number , middle , end);
            }else{
                if(number >= numberArray[start]){
                    return findNumber(numberArray , number , start , middle - 1);
                }
                return findNumber(numberArray , number , middle , end);
            }

        }else{
            //非正常序列，大于最后只，一定在后
            if(number <= numberArray[middle]){
                return findNumber(numberArray , number , start , middle - 1);
            }else{
                if(number <= numberArray[end]){
                    return findNumber(numberArray , number , middle , end);
                }
                return findNumber(numberArray , number , start , middle - 1);
            }
        }

    }

    public static void main(String[] args) {

//        int[] numberArray = new int[]{7,8,9,1,4,5};
        int[] numberArray = new int[]{7,8,9,10,14,15};

        NumberLocate numberLocate = new NumberLocate();
        int number = numberLocate.findNumber(numberArray, 9, 0, numberArray.length - 1);
        System.out.println(number);

    }
}
